package com.mlh.dp.子序列;

/**
 * @author 缪林辉
 * @date 2024/5/11 11:11
 * @DESCRIPTION
 */
// 给两个整数数组 nums1 和 nums2 ，返回 两个数组中公共的 、长度最长的连续子数组的长度 。
//    记住，子序列默认不连续，子数组默认连续
// 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
// 输出：3
// 解释：长度最长的公共子数组是 [3,2,1] 。
public class 最长重复子数组 {
    public int method1(int[] nums1, int[] nums2) {
        //数组含义：dp[i][j] 以下标为i结尾的数组与下标为j结尾的数组拥有的最长公共子数组的长度
        int[][]dp=new int[nums1.length+1][nums2.length+1];
        //递推公式 dp[i][j]=dp[i-1][j-1]+1 or 0
        //初始化  i=1 j=1 对于数组中下标0元素  之所以这样是方便处理边界
        // 根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
        // 但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
        // 所以dp[i][0] 和dp[0][j]初始化为0。
        // 举个例子A[0]如果和B[0]相同的话，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0，正好符合递推公式逐步累加起来。
        int res=0;
        for (int i = 1; i <=nums1.length; i++) {
            for (int j = 1; j <=nums2.length; j++) {
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                res=Math.max(dp[i][j],res);
            }
        }
        return res;
    }
}
